#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unsigned int a, b, k, w;
ll d[35][5][5][5][5][5];
/***
1
998244353 998244353 114514 123456789
53
 */

ll dp(int p, int v1, int v2, bool lw, bool lx, bool ly){
    v1 = min(v1, 1), v2 = min(v2, 1);
    if(p == -1) return v1 >=0 && v2>=0;
    if(v1 < -1 || v2 < -1) return 0;

//    if(v1 >=1 && v2>=1 && !lx && !ly && !lw)
//        return pow(1<<(p+1), 2);

    if(~d[p][v1+1][v2+1][lw][lx][ly])
        return d[p][v1+1][v2+1][lw][lx][ly];

    int ttt = a>>p;
    int tt = (a>>p)&1;
    int ma = lx?a>>p&1:1, mb = ly?b>>p&1:1;
    ll ans = 0;
    for (int x = 0; x <= ma; ++x) {
        for (int y = 0; y <= mb; ++y) {
            if(lw && (x^y)>(w>>p&1))
                continue;
            int t = k>>p&1;
            ans += dp(p-1, v1*2+y-x+t, v2*2+x-y+t, lw&&(x^y)==(w>>p&1), lx&&x==ma, ly&&y==mb);
        }
    }
    d[p][v1+1][v2+1][lw][lx][ly]= ans;
    return ans;
}


int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T; cin >> T;
//int T = 200;
    int s = clock();
    while (T--){
        memset(d, -1, sizeof d);
        cin >> a >> b >> k >> w;
        int pp = max(32-__builtin_clz(a), 32-__builtin_clz(b));
        cout << dp(31, 0, 0, true, true, true) << "\n";
    }
//    cout << (double)(clock()-s)/CLOCKS_PER_SEC << "\n";
    return 0;
}